public class questions {

    class TreeNode {
        public int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    class Solution {

        /**
         * 时间复杂度为：O(min(m,n))
         *
         * @param p m个节点
         * @param q n个节点
         * @return
         */
        public boolean isSameTree(TreeNode p, TreeNode q) {
            //1. 一个为空，一个不为空，必不一样
            if (p == null && q != null || p != null && q == null) {
                return false;
            }

            //2. 两个都为空
            if (p == null && q == null) {
                return true;
            }

            //3. 剩下的一种情况就是两个都不为空，不需要再用if限制条件了
            if (p.val != q.val) {
                return false;
            }

            //4. 此时代表两个都不为空，且 val 的值相等
            //5. 说明根节点相同，系接下来判断两棵树的左右是不是同时分别相同
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }


        /**
         * 判断子树
         *
         * @param p
         * @param q
         * @return
         */
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            //1. 若两棵树相同
            if (isSameTree(root, subRoot)) {
                return true;
            }
            //2. 不相等，判断是否是左子树的子树
            if (isSubtree(root.left, subRoot)) {
                return true;
            }
            //判断是否是右子树的子树
            if (isSubtree(root.right, subRoot)) {
                return true;
            }
            return false;
        }


        /**
         * 翻转二叉树
         *
         * @param root
         * @return
         */
        public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            if (root.left == null && root.right == null) {
                return root;
            }
            TreeNode ret = null;
            ret = root.right;
            root.right = root.left;
            root.left = ret;
            invertTree(root.left);
            invertTree(root.right);
            return root;
        }


        /**
         * 获取最大深度
         *
         * @param root
         * @return
         */
        public int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);

            return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
        }


        /**
         * 平衡二叉树
         *
         * @param root
         * @return
         */
        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            if (Math.abs(leftDepth - rightDepth) <= 1 &&
                    isBalanced(root.left) && isBalanced(root.right)) {
                return true;
            }
            return false;
        }


        /**
         * 对称二叉树
         *
         * @param root
         * @return
         */
        public boolean isSymmetric(TreeNode root) {
            if (root == null) return true;

            return isSymmetricChild(root.left, root.right);
        }

        public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
            //1. 检查结构是否相同
            //1.1 一个为空一个不为空
            if (leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
                return false;
            }
            //1.2 处理两个都为空和两个都不空的情况
            if (leftTree == null && rightTree == null) {
                return true;
            }
            //1.3 两个都不为空，判断他们的值一不一样
            if (leftTree.val != rightTree.val) {
                return false;
            }
            //此时两个节点都不为空，且值一样
            //2. 开始判断是否对称，需要满足
            // 左子树的左 和 右子树的右对称 通同时 左子树的右 和 右子树的左对称
            return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
        }


        
    }
}






